/*
 * The MIT License
 *
 * Copyright 2012 http://generic-toolset.googlecode.com.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */
package org.rlpw.lang;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;


/**
 * Comparator for Strings which provides nutural sorting
 *
 * Natural means in this case, that strings which you want to compare
 * will be splitted into chunks, depending if they are numeric parts
 * or not. Non-numerical chunks will be treated like normal like normal
 * Strings, while Numerical chunks get a special treatment.
 * The algorithm finds out which chunk represents a higher number in that
 * case. If a numerical chunk will be compared with a non-numerical one,
 * the numerical chunk will be seen as lower.
 */
public class NaturalComparator implements Comparator<String> {

    private boolean isDigit(char ch) {
        return ch > 47 && ch < 58;
    }

    private List<Chunk> getChunks(String input) {
        List<Chunk> chunks = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        boolean numeric = false;
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (numeric != isDigit(c)) {
                if (sb.length() > 0) {
                    chunks.add(new Chunk(sb.toString(), numeric));
                    sb = new StringBuilder();
                }
                numeric = !numeric;
            }
            sb.append(c);
        }
        if (sb.length() > 0) {
            chunks.add(new Chunk(sb.toString(), numeric));
        }
        return chunks;
    }

    @Override
    public int compare(String s1, String s2) {
        List<Chunk> ch1 = getChunks(s1);
        List<Chunk> ch2 = getChunks(s2);
        int n = Math.min(ch1.size(),ch2.size());

        for(int i = 0; i < n; i++) {
            int a = ch1.get(i).compareTo(ch2.get(i));
            if (a != 0) {
                return a;
            }
        }

        return ch1.size() - ch2.size();
    }

    private class Chunk implements Comparable<Chunk>{

        private String chunk;
        private boolean isNumber;

        public Chunk(String chunk, boolean isNumber) {
            this.chunk = chunk;
            this.isNumber = isNumber;
        }

        public boolean isNumber() {
            return isNumber;
        }

        public String getChunk() {
            return chunk;
        }

        public int length() {
            return chunk.length();
        }

        @Override
        public int compareTo(Chunk o) {
            if (isNumber == o.isNumber()) {
                if (isNumber) {
                    if (length() < o.length()) {
                        return -1;
                    } else if (length() > o.length()) {
                        return 1;
                    } else {
                        for (int i = 0; i < length(); i++) {
                            Character ct = chunk.charAt(i);
                            Character co = o.getChunk().charAt(i);
                            int a = ct.compareTo(co);
                            if (a != 0) {
                                return a;
                            }
                        }
                        return 0;
                    }
                } else {
                    return chunk.compareTo(o.getChunk());
                }
            } else {
                if (isNumber) {
                    return -1;
                } else {
                    return 1;
                }
            }
        }
    }
}